package org.nowcoder.leetcode.linkedList;

import java.util.HashMap;
import java.util.Map;

/**
 * Title  : 138. Copy List with Random Pointer
 * Source : https://leetcode.cn/problems/copy-list-with-random-pointer/?envType=study-plan-v2&envId=top-interview-150
 * Author : XrazYang
 * Date   : 2023-07-13
 */

public class LeetCode_138 {
    class Node {
        int val;
        Node next;
        Node random;

        public Node(int val) {
            this.val = val;
            this.next = null;
            this.random = null;
        }
    }

    public Node copyRandomList(Node head) {
        //难点： 处理随机指针
        Map<Node, Node> nodeMap = new HashMap<>(1024); // old -- new  对应关系
        Node copyHead = null, p = null;

        //1. 完成拷贝,并建立 old -- new 对应关系，random仍然指向旧的结点
        while (head != null) {
            Node node = new Node(head.val);
            node.random = head.random;
            if (copyHead == null) {
                copyHead = node;
            } else {
                p.next = node;
            }
            p = node;
            nodeMap.put(head, node);
            head = head.next;
        }
        //2. 更新random指向
        p = copyHead;
        while (p != null) {
            if (p.random != null) {
                p.random = nodeMap.get(p.random);
            }
            p = p.next;
        }
        return copyHead;
    }
}
